package com.cet.algorithm.二叉树.二叉树的最大深度;

/**
 * @program: algorithm
 * @description: 二叉树最大深度
 * @author: 陈恩涛
 * @create: 2022-07-19 15:16
 **/
public class LC104 {

    public static void main(String[] args) {
        final TreeNode root = new TreeNode(3, new TreeNode(4, new TreeNode(1), new TreeNode(2, new TreeNode(0), null)), new TreeNode(5));
        System.out.println(new LC104().maxDepth2(root));
    }

    /**
     * 递归法，后序遍历
     * @param root 根节点
     * @return 二叉树最大深度
     */
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        final int lDepth = maxDepth(root.left);
        final int rDepth = maxDepth(root.right);
        return 1 + Math.max(lDepth, rDepth);
    }

    int result;

    /**
     * 前序遍历，回溯法
     * @param root 根节点
     * @return 二叉树最大深度
     */
    public int maxDepth2(TreeNode root) {
        result = 0;
        if (root == null) {
            return result;
        }
        getDepth(root, 1);
        return result;
    }

    private void getDepth(TreeNode node, int depth) {
        result = depth > result ? depth : result;

        if (node.left == null && node.right == null) {
            return;
        }

        if (node.left != null) {
            depth++;
            getDepth(node.left, depth);
            depth--;
        }
        if (node.right != null) {
            depth++;
            getDepth(node.right, depth);
            depth--;
        }
        return;
    }

    // 迭代法见二叉树层级遍历

}
